package oj.hot100;

public class 最长回文子串 {
    //中心扩展算法 时间复杂度O(n*n),空间复杂度都是O(1)
    public String longestPalindromeEX(String s) {
        int begin = 0,len = 0;
        int n = s.length();
        for(int i = 0;i < n;i++) {
            //先计算子串为奇数个字符的情况.
            int left = i,right = i;
            while(left >= 0 && right < n) {
                if(s.charAt(left) != s.charAt(right)) {
                    break;
                }
                left--;
                right++;
            }
            if(right-left-1 > len) {
                begin = left+1;
                len = right-left-1;
            }
            //计算子串为偶数个字符的情况.
            left = i;
            right = i+1;
            while(left >= 0 && right < n) {
                if(s.charAt(left) != s.charAt(right)) {
                    break;
                }
                left--;
                right++;
            }
            if(right-left-1 > len) {
                begin = left+1;
                len = right-left-1;
            }
        }
        return s.substring(begin,begin+len);
    }
    //动态规划 时间复杂度和空间复杂度都是O(n*n)
    public String longestPalindrome(String ss) {
        int begin = 0,len = 0;
        char[] s = ss.toCharArray();
        int n = s.length,ret = 0;
        boolean[][] dp = new boolean[n][n];
        for(int i = n-1;i >= 0;i--) {
            for(int j = n-1;j >= i;j--) {
                if(s[i] != s[j]) {
                    dp[i][j] = false;
                }else {
                    if(i+1 ==j || i == j) {
                        dp[i][j] = true;
                    }else {
                        dp[i][j] = dp[i+1][j-1];
                    }
                }
                if(dp[i][j] && j-i+1 > len) {
                    begin = i;
                    len = j-i+1;
                }
            }
        }
        return ss.substring(begin,begin+len);
    }
}
